#include <stdio.h>
#include <stdlib.h>

// https://blog.csdn.net/it_is_me_a/article/details/99870530

// 定义结点类型
typedef enum
{
    atom, // atom=0; 表原子
    list  // list=1; 表子表
} NodeTag;

// 定义广义表结构
typedef struct glnode
{
    NodeTag tag; // 用于区分原子结点 和 表结点
    union        // 共用体，同一时刻只能保存一个成员的值
    {
        char data;            // 存放原子结点的值
        struct glnode *slink; // 指向子表的指针
    };
    struct glnode *next; // 指向下一个表结点
} GLNode, *GList;

// 创建广义表
GList createGList()
{
    GList GL;
    char ch;
    scanf("%c", &ch);
    printf("input>>%c\n", ch);
    if (ch != ' ')
    {
        GL = (GList)malloc(sizeof(GLNode));
        if (ch == '(')
        {
            printf(">>list start\n");
            GL->tag = list;
            // 递归构建子表
            GL->slink = createGList(GL->slink);
        }
        else if (')' == ch) // 当前字符为右括号
        {
            GL = NULL;
            printf("list end<<\n");
        }
        else
        {
            printf(">atom\n");
            GL->tag = atom;
            GL->data = ch;
        }
    }
    else
    {
        GL = NULL;
        printf("GL end\n");
    }

    // 如果不为空，则说明可能还有下一个结点
    if (GL != NULL)
    {
        scanf("%c", &ch);
        printf("next input>>%c\n", ch);
        // 若不等于逗号，则表明无下一个结点
        if (ch == ',')
        {
            printf(">has next-----");
            GL->next = createGList(GL->next);
        }
        else
        {
            printf(">no next-----");
            GL->next = NULL;
        }
    }
    return GL;
}

// 查找广义表中的元素
int findGList(GList GL, char x)
{
    if (GL == NULL)
    {
        printf("the gen list is empty\n");
        return 0;
    }
    // 如果是原子
    if (GL->tag == atom)
    {
        printf("it'is atom element: %c\n", GL->data);
        return GL->data == x;
    }
    else
    {
        printf("it'is list element\n");
        GList current = GL->slink;
        while (current != NULL)
        {
            int result = findGList(current, x);
            if (result)
            {
                return 1;
            }
            current = current->next;
        }

        return 0;
    }
}

// 求广义表的表头
GList head(GList GL)
{
    GList p;
    if (GL != NULL && GL->tag != atom)
    {
        p = GL->slink;
        p->next = NULL;
        return p;
    }

    return NULL;
}
// 求广义表的表尾
GList tail(GList GL)
{
    GList p;
    if (GL != NULL && GL->tag != atom)
    {
        p = GL->slink;
        p = p->next;   // 指向下一个元素
        GL->slink = p; // 删除第一个元素
    }

    return p;
}

// 求广义表的深度
int depth(GList GL)
{
    int maxdh = 0, dep;
    if (GL->tag == atom)
    {
        return 0;
    }
    // 子表为空，则深度为1
    GL = GL->slink;
    if (GL == NULL)
    {
        return 1;
    }
    while (GL != NULL)
    {
        if (GL->tag == list)
        {
            dep = depth(GL);
            if (dep > maxdh)
            {
                maxdh = dep;
            }
        }

        GL = GL->next;
    }
    return maxdh + 1;
}

// 求广义表的长度
int lenght(GList GL)
{
    int n = 0;
    GL = GL->slink;
    while (GL != NULL)
    {
        GL = GL->next;
        n++;
    }
    return n;
}

// 复制广义表
GList copy(GList GL)
{
    GList newGL;
    if (NULL == GL)
    {
        return NULL;
    }

    newGL = (GList)malloc(sizeof(GLNode));
    newGL->tag = GL->tag;
    if (GL->tag == list)
    {
        newGL->slink = copy(GL->slink);
    }
    else
    {
        newGL->data = GL->data;
    }

    newGL->next = copy(GL->next);
    return newGL;
}

// 打印广义表.
// 思想:若tag=list的结点，是一个子表的开始，则先打印左括号; 若子表为空, 则输出空格, 否则递归调用输出子表, 输出完后打印右括号。
void printGList(GList GL)
{
    if (GL == NULL)
    {
        printf("the gen list is empty\n");
        return;
    }
    // 如果为子表
    if (GL->tag == list)
    {
        printf("(");
        if (GL->slink == NULL)
        {
            // 输出空子表
            printf(" ");
        }
        else
        {
            // 递归输出子表
            printGList(GL->slink);
        }
    }
    else
    {
        printf("%c", GL->data);
    }

    if (GL->tag == list)
    {
        printf(")");
    }

    // 若还有下一个结点，则递归输出下一个结点
    if (GL->next != NULL)
    {
        printf(",");
        printGList(GL->next);
    }
}

int main()
{
    GList gl = createGList();
    printf("\n------------print glist-----------\n");
    printGList(gl);
    printf("\n");
    printf("GList length=%d\n", lenght(gl));
    printf("GList depth=%d\n", depth(gl));
    printf("GList head: ");
    GList forHead = copy(gl);
    printGList(head(forHead));
    printf("\nGList tail: (");
    GList forTail = copy(gl);
    printGList(tail(forTail));
    printf(")\n");
    // 释放复制的广义表
    free(forHead);
    free(forTail);

    printf("\n>input need find element: ");
    char in = getchar();
    int result = findGList(gl, in);
    printf(">the find [%c] result: %s\n", in, result ? "yes" : "no");
    return 0;
}